package algorithm

import "sort"

func permutation(num int) []int {
	var nums []int
	tmp := num
	for tmp != 0 {
		nums = append(nums, tmp%10)
		tmp /= 10
	}

	sort.Ints(nums)

	var ret []int
	var track, cnt int
	var backtrack func()
	used := make([]bool, len(nums))

	backtrack = func() {
		if cnt == len(nums) {
			if track != num {
				ret = append(ret, track)
			}
			return
		}

		for i := 0; i < len(nums); i++ {
			if used[i] {
				continue
			}

			if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
				continue
			}

			if track == 0 && nums[i] == 0 {
				continue
			}

			track = track*10 + nums[i]
			cnt++
			used[i] = true

			backtrack()

			track = (track - nums[i]) / 10
			cnt--
			used[i] = false
		}
	}

	backtrack()
	return ret
}
